package 数据结构和算法.剑指offer.数组.数组中重复的数字;

import java.util.HashSet;
import java.util.Set;

/**
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
 * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
 * 请找出数组中任意一个重复的数字。
 * <p>
 * 暴力法：即通过遍历数组的方式去判断是否有重复的数字，缺点是时间复杂度大，基本是O(n^2)的级别；
 * 异或法：利用异或的特性，相同是0，不同为1，可以筛选出数组中不重复的数字；
 * HashSet：利用集合的元素唯一的性质，可以找出数组中重复的数字。
 */
public class Test {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 1};
        System.out.printf(String.valueOf(findRepeatNumber(array)));
    }


    public static int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int repeat = -1;
        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;
    }
}
